package com.le.high.class4;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。
 * 再给定一个正数 limit，代表一艘船的载重。
 * 以下是坐船规则，
 * 1）每艘船最多只能做两人；
 * 2）乘客 的体重和不能超过limit。
 * 返回如果同时让这N个人过河最少需要几条船。
 */
public class Problem01_MinBoat {

    // 请保证arr有序
    public static int minBoat1(int[] arr, int weight) {
        if (arr == null || arr.length == 0 || weight < 0) {
            return 0;
        }
        int lessR = -1;
        // 第一个数都大于weight/2,说明每个人一条船
        if (arr[0] > (weight / 2)) {
            return arr.length;
        }
        // 最后一个数都小于weight/2，说明任意两个人都可乘坐一条船
        if (arr[arr.length - 1] < (weight / 2)) {
            return arr.length / 2;
        }
        for (int i = arr.length - 1; i > -1; i--) {
            if (arr[i] <= (weight / 2)) {
                lessR = i;
                break;
            }
        }
        if (lessR == -1) {
            return arr.length;
        }
        int left = lessR; // 小于等于weight/2 最右位置
        int right = lessR + 1;
        int solved = 0; // 已经解决个数
        int unSolved = 0; // 小于weight/2 但不能解决个数
        int unUsed = 0; // 大于weight /2 ，不能解决个数
        while (left > -1) {
            while (right < arr.length && left > -1 && arr[left] + arr[right] <= weight) {
                solved++;
                right++;
                left--;
            }
            if (left > -1 && right < arr.length && arr[left] != arr[right]) {
                unSolved++;
                left--;
            }
        }
        if (right < arr.length) {
            unUsed = arr.length - right;
        }
        return solved + ((unSolved + 1) >> 1) + unUsed;
    }

    // 请保证arr有序
    public static int minBoat(int[] arr, int weight) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int lessR = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= (weight / 2)) {
                lessR = i;
                break;
            }
        }
        if (lessR == -1) {
            return arr.length;
        }
        int lessIndex = lessR;
        int moreIndex = lessR + 1;
        int lessUnused = 0;
        while (lessIndex >= 0) {
            int solved = 0;
            while (moreIndex < arr.length
                    && arr[lessIndex] + arr[moreIndex] <= weight) {
                moreIndex++;
                solved++;
            }
            if (solved == 0) {
                lessUnused++;
                lessIndex--;
            } else {
                lessIndex = Math.max(-1, lessIndex - solved);
            }
        }
        int lessAll = lessR + 1;
        int lessUsed = lessAll - lessUnused;
        int moreUnsolved = arr.length - lessR - 1 - lessUsed;
        return lessUsed + ((lessUnused + 1) >> 1) + moreUnsolved;
    }

    public static int[] generateArray() {
        int[] res = new int[20];
        for (int i = 0; i < res.length; i++) {
            res[i] = (int) (Math.random() * 100) + 1;
        }
        bucketSort(res);
        return res;
    }

    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        int[] br = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            br[arr[i]]++;
        }
        int j = 0;
        for (int i = 0; i < br.length; i++) {
            while (br[i]-- > 0) {
                arr[j++] = i;
            }
        }
    }


    @Test
    public void test() {
//        int[] arr = {1, 2, 2, 2, 2, 4, 4, 4, 4, 5};
//        int weight = 5;
//        System.out.println("test01");
//        System.out.println(minBoat(arr, weight));
//        System.out.println(minBoat1(arr, weight));
//        int[] arr1 = {1, 1, 3, 3, 3, 4, 4, 5, 5, 5, 7, 7, 9, 9, 9};
//        int weight1 = 10;
//        System.out.println("test02");
        for (int i = 0; i < 100; i++) {
            int[] res = generateArray();
            int weight = (int) (Math.random() * 100) + 1;
            if (minBoat(res, weight) != minBoat1(res, weight)) {
                System.out.println(Arrays.toString(res));
                System.out.println(weight);
                break;
            }
        }


    }
}
